package leetcode

func maxProfitDP(prices []int) int {
	count := len(prices)
	if count < 2 {
		return 0
	}

	num := 2
	dp := make([][]int, num+1)

	dp[0] = make([]int, count)
	for k := 1; k <= num; k++ {
		tmpMax := dp[k-1][0] - prices[0]
		dp[k] = make([]int, count)
		for i := 1; i < count; i++ {
			if dp[k][i-1] < prices[i]+tmpMax {
				dp[k][i] = prices[i] + tmpMax
			} else {
				dp[k][i] = dp[k][i-1]
			}

			if tmpMax < dp[k-1][i]-prices[i] {
				tmpMax = dp[k-1][i] - prices[i]
			}
		}
	}
	return dp[num][count-1]
}

func maxProfit(prices []int) int {
	count := len(prices)
	if count < 2 {
		return 0
	}

	left, right := make([]int, count), make([]int, count)

	min := prices[0]
	for i := 1; i < count; i++ {
		if min > prices[i] {
			min = prices[i]
		}

		if prices[i]-min > left[i-1] {
			left[i] = prices[i] - min
		} else {
			left[i] = left[i-1]
		}
	}

	max := prices[count-1]
	for i := count - 2; i >= 0; i-- {
		if max < prices[i] {
			max = prices[i]
		}

		if max-prices[i] > right[i+1] {
			right[i] = max - prices[i]
		} else {
			right[i] = right[i+1]
		}
	}

	sum := left[0] + right[0]
	for i := 1; i < count; i++ {
		if sum < left[i]+right[i] {
			sum = left[i] + right[i]
		}
	}
	return sum
}
